 public class LinkedList {
     static class linked{
          int val;
          linked prev;
          linked next;
          public linked(int val){
               this.val=val;

          }


     }
      public linked head;
      public linked tail;
      LinkedList() {


                tail = head ;



      }

     //头插法
     public void addFirst(int data){
          linked cur=new linked(data);
          if(head==null){
               head=cur;



          }else{
               cur.next=head;
               head.prev=cur;
          }


     }
     //尾插法
     public void addLast(int data){
          linked cur=new linked(data);
          if(head==null){
               head=cur;

          }else{
               tail.next=cur;
               cur.prev=tail;
               tail=cur;


          }

     }
     //任意位置插入,第一个数据节点为0号下标
     public boolean addIndex(int index,int data){
          if(index < 0 || index > size()) {

               System.out.println("index不合法！");

               return false;

          }
          if(index == 0) {

               addFirst(data);

               return false;

          }
          linked cur=new linked(data);
          linked find=head;
          while(index-->0){
               find=find.next;
          }
          find.prev.next=cur;
          cur.prev=find.prev;
          cur.next=find;
          find.prev=cur;
          return true;



     }
     //查找是否包含关键字key是否在单链表当中
     public boolean contains(int key){
           if(head==null){
                return  false;

           }
           linked find =head;
           while(find!=null){
                if(find.val==key){
                     return true;
                }
                find=find.next;
           }

           return false;
     }
     //删除第一次出现关键字为key的节点
     public void remove(int key){
           linked find=head;
           while(find!=null){
                if(find.val==key&&find.next!=null){
                     find.prev.next=find.next;
                     find.next.prev=find.prev;
                     return;

                }else if(find.val==key&&find.next==null){
                     find.prev.next=null;
                     return;

                }
                find=find.next;
           }
           if(find==null){
                System.out.println("no find key value");
           }

     }
     //删除所有值为key的节点
     public void removeAllKey(int key){
          linked find=head;
          while(find!=null){
               if(find.val==key&&find.next!=null){
                    find.prev.next=find.next;
                    find.next.prev=find.prev;


               }else if(find.val==key&&find.next==null){
                    find.prev.next=null;


               }
               find=find.next;
          }

               System.out.println("no find key value");


     }
     //得到单链表的长度
     public int size(){
           linked count=head;
           int len=0;
           while(count!=null){
                len++;

                count=count.next;
           }
           return len;
     }
     public void display(){
           linked pri=head;
           while(pri!=null){
                System.out.println(pri.val+" ");
           }

     }
     public void clear(){
          linked cur = head;
          while (cur != null) {

            linked curNext = cur.next;

               ///cur.val = null;

               cur.prev = null;

               cur.next = null;

               cur = curNext;

          }

          head = null;

         tail = null;

     }


 }
